"""
Problem 98: https://projecteuler.net/problem=98

By replacing each of the letters in the word CARE with 1, 2,
9, and 6 respectively, we form a square number: 1296 = 362.
What is remarkable is that, by using the same digital
substitutions, the anagram, RACE, also forms a square number:
9216 = 962. We shall call CARE (and RACE) a square anagram
word pair and specify further that leading zeroes are not
permitted, neither may a different letter have the same
digital value as another letter.

Using words.txt (right click and 'Save Link/Target As...'),
a 16K text file containing nearly two-thousand common English
words, find all the square anagram word pairs (a palindromic
word is NOT considered to be an anagram of itself).

What is the largest square number formed by any member of
such a pair?

NOTE: All anagrams formed must be contained in the given
text file.
"""

from collections import Counter
WordsFile = 'p098_words.txt'
with open(WordsFile, 'r') as fp:
    Words = eval('[' + fp.read().strip() + ']')
# print(Words)

WordsDict = {word: Counter(word) for word in Words}
# print(WordsDict)

WordsGroup = []
while Words:
    word = Words.pop()
    sameVals = set()
    for key, val in WordsDict.items():
        if val == WordsDict[word]:
            sameVals.add(key)

    if sameVals not in WordsGroup and len(sameVals) >= 2:
        WordsGroup.append(sameVals)


WordsGroup = [list(wg) for wg in WordsGroup]
print('WordsGroup:\n', WordsGroup)


def findSquarePair(wordsgroup: list):
    '''
    >>> print(findSquarePair(['CARE', 'RACE']))
    9216
    '''
    lens = len(wordsgroup[0])
    candiates = [str(i*i) for i in range(int((10**(lens-1))**0.5),
                                         int((10**lens)**0.5)+1)]

    # print(candiates)

    for cand in candiates[::-1]:
        if len(cand) != lens:
            continue

        # a different letter have the same digital value as another letter
        if len(set(wordsgroup[0])) != len(set(cand)):
            continue
        sol = dict(zip(wordsgroup[0], cand))
        if len(set(sol.keys())) > len(set(sol.values())):
            continue

        # every anagrams form a square number
        for otherword in wordsgroup[1:]:
            num = ''.join(map(lambda c: sol[c], otherword))
            if num not in candiates:
                break
        else:
            return int(cand)

    return 0


def solution():
    squareNum = 0
    words = None
    for wg in WordsGroup:
        tmp = findSquarePair(wg)
        print(wg, tmp)
        if tmp > squareNum:
            squareNum = tmp
            words = wg

    return words, squareNum


if __name__ == "__main__":
    from doctest import testmod

    testmod()
    print(solution())
    # (['BROAD', 'BOARD'], 18769)
